export class TreeNode {
    val: number
    left: TreeNode | null
    right: TreeNode | null
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = (val === undefined ? 0 : val)
        this.left = (left === undefined ? null : left)
        this.right = (right === undefined ? null : right)
    }
    // 打印树的前序列化
    static printPreTree(root: TreeNode | null): string {
        let seri = ''
        if (!root) return '#'
        seri += root.val
        const left = this.printPreTree(root.left)
        const right = this.printPreTree(root.right)
        seri = root.val + ',' + left + ',' + right
        return seri
    }
    // 打印树的层序遍历序列化
    static printTree(root: TreeNode | null): any {
        let queue = [], res = []
        if (root) queue.push(root)
        while (queue.length) {
            for (let i = 0; i < queue.length; i++) {
                const node: any = queue.shift()
                if (!node) {
                    res.push(-1)
                } else {
                    res.push(node.val)
                    queue.push(node.left ?? null)
                    queue.push(node.right ?? null)
                }
            }
        }
        while (res[res.length - 1] === -1) {
            res.pop()
        }
        return res
    }
    static buildTree(preorder: Array<number | null>): TreeNode | null {
        if (!preorder.length) return null
        const root = new TreeNode(preorder.shift() ?? undefined)
        let list = [root]
        while (preorder.length) {
            const tmpList = []
            for (let i = 0; i < list.length; i++) {
                const p = list[i]
                const left = preorder.length ? preorder.shift() : null
                if (left !== null) {
                    p.left = new TreeNode(left)
                }
                const right = preorder.length ? preorder.shift() : null
                if (right !== null) {
                    p.right = new TreeNode(right)
                }
                if (p.left) {
                    tmpList.push(p.left)
                }
                if (p.right) {
                    tmpList.push(p.right)
                }
            }
            list = tmpList
        }
        return root
    }
}

export class ListNode {
    val: number
    next: ListNode | null
    constructor(val?: number, next?: ListNode | null) {
        this.val = (val === undefined ? 0 : val)
        this.next = (next === undefined ? null : next)
    }
    static printList(head: ListNode | null): string {
        let str = ''
        while (head) {
            str += head.val
            if (head.next) {
                str += ' -> '
            }
            head = head.next
        }
        return str
    }
}

class PQNode {
    val: any
    priority: any
    constructor(val: any, priority: any) {
        this.val = val
        this.priority = priority
    }
}
// 优先队列（最小堆）
export class PriorityQueue {
    values: any
    constructor() {
        this.values = []
    }

    enqueue(val: any, priority: any) {
        let node = new PQNode(val, priority)
        this.values.push(node)
        this.bubbleUp()
    }

    dequeue() {
        let max = this.values[0]
        let end = this.values.pop()
        if (this.values.length) {
            this.values[0] = end
            this.bubbleDown()
        }
        return max.val
    }

    isEmpty() {
        return !this.values.length
    }

    bubbleUp(index = this.values.length - 1) {
        if (index <= 0) return
        let parentIndex = Math.floor((index - 1) / 2)
        if (this.values[index].priority <= this.values[parentIndex].priority) {
            [this.values[index], this.values[parentIndex]] = [this.values[parentIndex], this.values[index]]
            this.bubbleUp(parentIndex)
        }
    }

    bubbleDown(index = 0, swapIndex: any = null) {
        let leftIndex = index * 2 + 1,
            rightIndex = index * 2 + 2,
            length = this.values.length

        if (leftIndex < length) {
            if (this.values[leftIndex].priority <= this.values[index].priority) {
                swapIndex = leftIndex
            }
        }

        if (rightIndex < length) {
            if ((swapIndex === null && this.values[rightIndex].priority <= this.values[index].priority) || (swapIndex !== null && this.values[rightIndex].priority <= this.values[leftIndex].priority)) {
                swapIndex = rightIndex
            }
        }

        if (swapIndex !== null) {
            [this.values[index], this.values[swapIndex]] = [this.values[swapIndex], this.values[index]]
            this.bubbleDown(swapIndex, null)
        }
    }
}

//  双向链表节点
export class Node {
    val: number
    prev: Node | null
    next: Node | null
    child: Node | null
    constructor(val?: number, prev?: Node, next?: Node, child?: Node) {
        this.val = (val === undefined ? 0 : val)
        this.prev = (prev === undefined ? null : prev)
        this.next = (next === undefined ? null : next)
        this.child = (child === undefined ? null : child)
    }
    static printList(head: Node | null): string {
        let str = ''
        while (head) {
            str += head.val
            if (head.next) {
                str += ' -> '
            }
            head = head.next
        }
        return str
    }
}

export class UF {
    count: number
    parent: number[]
    size: number[]
    constructor(n: number) {
        this.count = n
        this.parent = new Array(n).fill(0)
        this.size = new Array(n).fill(1)
        for (let i = 0; i < n; i++) {
            this.parent[i] = i
        }
    }
    // 返回x的根节点
    find(x: number): number {
        while (this.parent[x] !== x) {
            // 路径压缩
            this.parent[x] = this.parent[this.parent[x]]
            x = this.parent[x]
        }
        return x
    }
    // 将p、q联通
    union(p: number, q: number) {
        const rootP = this.find(p)
        const rootQ = this.find(q)
        if (rootP === rootQ) return
        if (this.size[rootP] > this.size[rootQ]) {
            this.parent[rootQ] = rootP
            this.size[rootP] += this.size[rootQ]
        } else {
            this.parent[rootP] = rootQ
            this.size[rootQ] += this.size[rootP]
        }
        this.count--
    }
    // 判断p、q是否联通
    connnect(p: number, q: number): boolean {
        const rootP = this.find(p)
        const rootQ = this.find(q)
        return rootP === rootQ
    }
}
